import org.junit.jupiter.api.Test;

import javax.accessibility.AccessibleHyperlink;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author ZhengDp
 * @Date 2023/4/18 18:46
 */
public class 动态规划 {
    /*
     * #problem 62 不同路径
     * */
    // 1. 傻递归 - 超时
    public int uniquePaths(int m, int n) {
        return dfs(m, n, 1, 1);
    }

    private int dfs(int m, int n, int x, int y) {
        if (m == x && n == y) {
            return 1;
        }
        if (x > m || y > n) {
            return 0;
        }
        return dfs(m, n, x + 1, y) + dfs(m, n, x, y + 1);
    }

    // 2. 记忆化搜索
    public int uniquePaths2(int m, int n) {
        int[][] memo = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                memo[i][j] = -1;
            }
        }
        return dfs(m, n, 1, 1, memo);
    }

    private int dfs(int m, int n, int x, int y, int[][] memo) {
        if (x > m || y > n) {
            return 0;
        }
        if (memo[x][y] != -1) {
            return memo[x][y];
        }
        if (m == x && n == y) {
            return 1;
        }
        memo[x][y] = dfs(m, n, x + 1, y, memo) + dfs(m, n, x, y + 1, memo);
        return memo[x][y];

    }

    // 3. 动态规划-自底向上
    public int uniquePaths3(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        Arrays.fill(dp[m], 1);
        for (int i = 1; i < m; i++) {
            dp[i][n] = 1;
        }
        for (int i = m - 1; i >= 1; i--) {
            for (int j = n - 1; j >= 1; j--) {
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }

        return dp[1][1];
    }

    // 4. 动态规划-空间优化
    public int uniquePaths4(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                dp[j] += dp[j + 1];
            }
        }

        return dp[0];
    }

    /*
     * #problem 63 不同路径II
     * 带障碍物
     * */
    @Test
    void uniquePathsWithObstaclesTest() {
        uniquePathsWithObstacles(new int[][]{{0, 1}});
    }

    // 1. DFS
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return dfs(obstacleGrid, 0, 0);
    }

    private int dfs(int[][] obstacleGrid, int x, int y) {
        if (x >= obstacleGrid.length || y >= obstacleGrid[0].length) {
            return 0;
        }
        if (x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1) {
            return 1;
        }
        if (obstacleGrid[x][y] == 1) {
            return 0;
        }

        return dfs(obstacleGrid, x + 1, y) + dfs(obstacleGrid, x, y + 1);
    }

    // 2.DFS+记忆化搜索
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int[][] memo = new int[obstacleGrid.length][obstacleGrid[0].length];
        for (int i = 0; i < memo.length; i++) {
            for (int j = 0; j < memo[0].length; j++) {
                memo[i][j] = -1;
            }
        }
        return dfs(obstacleGrid, 0, 0, memo);
    }

    private int dfs(int[][] obstacleGrid, int x, int y, int[][] memo) {
        if (x >= obstacleGrid.length || y >= obstacleGrid[0].length) {
            return 0;
        }
        if (memo[x][y] != -1) {
            return memo[x][y];
        }
        if (x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1) {
            return 1;
        }
        if (obstacleGrid[x][y] == 1) {
            return 0;
        }
        memo[x][y] = dfs(obstacleGrid, x + 1, y, memo) + dfs(obstacleGrid, x, y + 1, memo);
        return memo[x][y];
    }

    // 3. 动态规划
    public int uniquePathsWithObstacles3(int[][] obstacleGrid) {
        int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[m - 1][i] != 1) {
                dp[m - 1][i] = 1;
            }
        }
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][n - 1] != -1) {
                dp[i][n - 1] = 1;
            }
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
                }
            }
        }

        return dp[0][0];
    }

    // 4. 动态规划-空间优化
    public int uniquePathsWithObstacles4(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            if (obstacleGrid[m - 1][i] == 1) {
                break;
            }
            dp[i] = 1;
        }
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                } else {
                    dp[j] += dp[j + 1];
                }
            }
        }
        return dp[0];
    }

    /*
     * #problem 1143. 最长公共子序列
     * */
    // 1. 动态规划
    // dp[i][j] ==> 以text1[i] 结尾和以 text2[j]结尾的字符串的最长公共子序列
    // dp[i][j] ==> if text1[i] == text2[j] ==> dp[i][j] = dp[i-1][j-1] + 1
    // if text1[i] != text2[j] ==> Math.max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])
    // ===> 因为 dp[i-1][j] dp[i][j-1] 有包括 dp[i-1][j-1] ，所以不需要比较 dp[i-1][j-1]
    public int longestCommonSubsequence(String text1, String text2) {
        int n1 = text1.length(), n2 = text2.length();
        int[][] dp = new int[n1][n2];
        if (text1.charAt(0) == text2.charAt(0)) {
            dp[0][0] = 1;
        }
        int fill = 0;
        for (int i = 0; i < n2; i++) {
            if (text1.charAt(0) == text2.charAt(i)) {
                fill = 1;
            }
            dp[0][i] = fill;
        }
        fill = 0;
        for (int i = 0; i < n1; i++) {
            if (text1.charAt(i) == text2.charAt(0)) {
                fill = 1;
            }
            dp[i][0] = fill;
        }
        for (int i = 1; i < n1; i++) {
            for (int j = 1; j < n2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n1 - 1][n2 - 1];
    }


    /*
     * #problem 120 三角形最小路径和
     * */
    public int minimumTotal(List<List<Integer>> triangle) {
        List<Integer> dp = new ArrayList<>(triangle.get(triangle.size() - 1));
        for (int i = triangle.size() - 2; i >= 0; i--) {
            List<Integer> cur = triangle.get(i);
            for (int j = 0; j < cur.size(); j++) {
                dp.set(j, Math.min(dp.get(j), dp.get(j + 1)) + cur.get(j));
            }
        }
        return dp.get(0);

    }

    /*
     * #problem 53 最大子数组和
     * */
    // 1. 动态规划 ==> dp[i] --> 以nums[i]为结尾的连续子数组的最大和的值
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        }
        int max = Integer.MIN_VALUE;
        for (int t : dp) {
            max = Math.max(t, max);
        }
        return max;

    }

    /*
     * #problem 152 乘积最大子数组
     * 与53题一样的思路(不对，乘积有负负得正的）
     * */
    public int maxProduct(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][2];
        // 0 : 最大值 1:最小值
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        for (int i = 1; i < len; i++) {
            if (nums[i] < 0) {
                dp[i][0] = Math.max(dp[i - 1][1] * nums[i], nums[i]);
                dp[i][1] = Math.min(dp[i - 1][0] * nums[i], nums[i]);
            } else {
                dp[i][0] = Math.max(dp[i - 1][0] * nums[i], nums[i]);
                dp[i][1] = Math.min(dp[i - 1][1] * nums[i], nums[i]);
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i++) {
            max = Math.max(max, dp[i][0]);
        }
        return max;

    }

    /*
     * #problem 322 零钱兑换
     * */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int k = i - coin;
                if (k >= 0) {
                    min = Math.min(min, dp[k] + 1);
                }
            }
            dp[i] = min == Integer.MAX_VALUE ? -1 : min;
        }
        return dp[amount];
    }

    /*
     * #problem 198 打家劫舍
     * */
    // 1. 动态规划 --> dp[i][0] : 不偷窃第i间房子 ==> dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1])
    // 如果不偷窃第i间房子，那么此时最大的偷窃金额应该从前一间房子的最大金额种得到
    // dp[i][1] : 偷窃第i间房子 ==> dp[i][0] = Math.max(dp[i-1][0]+nums[i])
    public int rob(int[] nums) {
        int len = nums.length;
        int[][] dp = new int[len][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }

    // 2. 动态规划 --> dp[i] ==> 第i间房子的偷窃最大值（需要比较是否偷窃第i间房子的偷窃最大值）
    // dp[i] ==> 有两种情况 ： 偷第i间房子和不偷第i间房子
    // 如果不偷第i间房子,此时的偷窃值等于 dp[i-1]
    // 如果偷第i间房子，那么此时i-1房子不应该被偷窃，此时的偷窃值应该等于 dp[i-2]+nums[i]
    public int rob2(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[len - 1];
    }

    /*
     * #problem 打家劫舍II
     * */
    // 1. 动态规划
    // 如果偷窃了第一间房子，那么就不能偷窃最后一间房子 ==> [0,len-2]
    // 如果没有偷窃第一间房子，那么就可以偷窃最后一间房子 ==> [1,len-1]
    public int rob3(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robHelper(len - 2, nums, 0), robHelper(len - 1, nums, 1));
    }

    private int robHelper(int right, int[] nums, int start) {
        int x_2 = nums[start], x_1 = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= right; i++) {
            int t = x_1;
            x_1 = Math.max(x_2 + nums[i], x_1);
            x_2 = t;
        }
        return x_1;
    }

    // 2. 动态规划2
    public int rob4(int[] nums) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        } else if (len == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(robHelper(0, len - 2, nums, 0), robHelper(1, len - 1, nums, 1));
    }

    private int robHelper(int left, int right, int[] nums, int start) {
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= right; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[right];
    }

    /*
     * #problem 121 买卖股票的最佳时机
     * */
    // 1. 暴力求解 --> 超时
    public int maxProfit(int[] prices) {
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < prices.length; i++) {
            for (int j = 0; j < i; j++) {
                max = Math.max(max, prices[i] - prices[j]);
            }
        }
        return max >= 0 ? max : 0;
    }

    // 2. 动态规划
    /*
     * dp[i] ==> prices[0..i] 的最小值
     * */
    public int maxProfit2(int[] prices) {
        int max = 0;
        int len = prices.length;
        int[] dp = new int[len];
        dp[0] = prices[0];
        for (int i = 1; i < len; i++) {
            dp[i] = Math.min(dp[i - 1], prices[i]);
            max = Math.max(max, prices[i] - dp[i]);
        }
        return max;
    }

    /*
     * #problem 122 买卖股票的最佳时机II
     * */
    // 1. 动态规划
    /*
     * dp[i][0] : 在第i天，未持有股票时的最大利润值
     * dp[i][1] : 在第i天，持有股票时的最大利润值
     * dp[i][0] = 第i天的未持有股票的状态可以从第i-1天推导得来，第i-1天时持有股票的最大利润+第i天抛出股票得到的利润 与 第i-1天未持有股票的最大利润进行比较
     * dp[i][1] = 第i天的持有股票的状态可以从第i-1天推到得来，第i-1天未持有股票的最大利润-第i天买入股票的钱 与 第i-1天持有股票的最大利润进行比较
     * */
    public int maxProfitII(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);
    }

    // 2. 动态规划-空间优化
    public int maxProfitII2(int[] prices) {
        int d0 = 0, d1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int t = d0;
            d0 = Math.max(d1 + prices[i], d0);
            d1 = Math.max(t - prices[i], d1);
        }
        return Math.max(d0, d1);
    }

    /*
     * #problem 123 买卖股票的最佳时机III
     * */
    // 1. 动态规划
    /*
     * 任意一天结束后，会处于五个状态
     * - 未进行过任何操作 （此时利润一直为0，因此不记录该状态）
     * - 第一次进行买操作
     * - 第一次进行卖操作 （一次交易结束）
     * - 第二次进行买操作
     * - 第二次进行卖操作
     * */
    public int maxProfitIII(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][4];
        dp[0][0] = -prices[0];
        // 第一天买入卖出，然后又买入
        dp[0][2] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[0]);
            dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
        }
        int max = 0;
        for (int i = 0; i < 4; i++) {
            max = Math.max(max, dp[len - 1][i]);
        }
        return max;
    }


    /*
     * #problem 309. 最佳买卖股票时机含冷冻期
     * */
    // 1. 动态规划
    /*
     * 任意一天结束后，处于如下状态
     * - 无任何操作
     * - 持有一只股票
     * - 不持有一只股票，且不处于冰冻期
     * - 不持有股票，且处于冰冻期（i处于冰冻期，则i+1不能买入股票） (第i天卖出股票，就会处于冰冻期）
     * */
    public int maxProfitFreeZe(int[] prices) {
        int len = prices.length;
        if (len <= 1) {
            return 0;
        }
        int[][] dp = new int[len][3];
        dp[0][1] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            // i-1处于冰冻期，i就不处于冰冻期
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        int max = 0;
        for (int i = 0; i < 3; i++) {
            max = Math.max(max, dp[len - 1][i]);
        }
        return max;

    }

    /*
     * #problem 188. 买卖股票的最佳时机 IV
     * */
    // 1. 动态规划
    /*
     *  - 无任何操作
     *  - 第一次买入
     *  - 第一次卖出
     * - 第二次买入
     * ...
     * - 第k次买入
     * - 第k次卖出
     * */
    public int maxProfitIV(int k, int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2 * k];
        for (int i = 0; i < 2 * k; i++) {
            if (i % 2 == 0) {
                dp[0][i] = -prices[0];
            }
        }
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            for (int j = 2; j < 2 * k; j += 2) {
                int j2 = j + 1;
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                dp[i][j2] = Math.max(dp[i - 1][j2], dp[i - 1][j] + prices[i]);
            }
        }
        int max = 0;
        for (int i = 0; i < 2 * k; i++) {
            max = Math.max(max, dp[len - 1][i]);
        }
        return max;
    }

    /*
     * #problem 714. 买卖股票的最佳时机含手续费
     * */
    // 1. 动态规划
    /*
     * 任意一天结束后，状态
     * - 持有股票的最大利润
     * - 不持有股票的最大利润
     * 每次卖出股票时都需要扣除手续费
     * */
    public int maxProfitServiceCharge(int[] prices, int fee) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        for (int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return Math.max(dp[len - 1][0], dp[len - 1][1]);

    }

    /*
     * #problem 279 完全平方数
     * */
    // 1. 动态规划
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            // j*j 就是一个完全平方数
            // dp[i-j*j] ==> 距离i只有一个完全平方数的差值的那个数，需要的最少完全平方数
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }

            dp[i] = min + 1;
        }
        return dp[n];

    }

    // 2. BFS
    public int numSquares2(int n) {
        Deque<Integer> q = new LinkedList<>();
        q.offer(0);
        Set<Integer> visited = new HashSet<>();
        int level = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            level++;
            while (sz-- > 0) {
                // 找到当前值的子结点（也就是加上完全平方数后的值）
                int curVal = q.poll();
                for (int i = 1; i * i <= n; i++) {
                    int nextVal = curVal + i * i;
                    if (nextVal > n) {
                        break;
                    }
                    if (nextVal == n) {
                        return level;
                    }
                    if (visited.contains(nextVal)) {
                        continue;
                    }
                    visited.add(nextVal);
                    q.offer(nextVal);
                }
            }
        }
        return 0;
    }

    /*
     * #problem 72 编辑距离
     * */
    /*
     * 单词 word1 和 word2 可以双向改变
     * A可以插入，删除和替换
     * B也可以插入，删除和替换
     * 不过 A往末尾加入一个字符，与B往末尾删除一个字符是等价的。
     * 同理 B往末尾加入一个字符与A往末尾删除一个字符是等价的。
     * 而对A替换一个字符与对B替换一个字符的操作是等价的。
     * 因此只有三种操作
     * A插入，B插入，A替换
     * 我们要求 A->B的最小编辑距离 ，那么我们可以从下面三个状态种得到
     * - A->B-1 + A-Insert  ==> A转换到B-1的最小编辑距离 + A插入一个字符 得到B
     * - B->A-1 + B-Insert ==> B转到到A-1的最小编辑距离 + B插入一个字符 得到A
     * - A-1 -> B-1 + A-Repliace ==> A-1转换到B-1的最小编辑距离 + A替换一个字符得到B
     * */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        // 考虑空字符串的情况，作为边界条件
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                int a_insert = dp[i][j - 1] + 1;
                int b_insert = dp[i - 1][j] + 1;
                int a_repliace = dp[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    a_repliace += 1;
                }
                dp[i][j] = Math.min(a_insert, Math.min(b_insert, a_repliace));
            }
        }
        return dp[len1][len2];

    }

    /*
     * #problem 55 跳跃游戏
     * */
    // 1. 动态规划 （也可以用贪心-->这边就不用贪心了）
    public boolean canJump(int[] nums) {
        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[0] = true;
        for (int i = 0; i < len - 1; i++) {
            if (!dp[i]) {
                continue;
            }
            int k = i + nums[i];
            for (int j = i + 1; j <= k && j < len; j++) {
                dp[j] = true;
            }
        }
        return dp[len - 1];
    }

    /*
     * #problem 45 跳跃游戏II
     * */
    // 1. 动态规划
    public int jump(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i < len; i++) {
            if (dp[i] == Integer.MAX_VALUE) {
                continue;
            }
            int k = i + nums[i];
            for (int j = i + 1; j <= k && j < len; j++) {
                dp[j] = Math.min(dp[j], dp[i] + 1);
            }
        }
        return dp[len - 1];
    }

    /*
     * #problem 980 不同路径 III
     * */
    // 1. DFS
    private int[] rows = new int[]{1, -1, 0, 0};
    private int[] cols = new int[]{0, 0, 1, -1};
    private int ans = 0;

    public int uniquePathsIII(int[][] grid) {
        int todo = 0;
        int sx = 0, sy = 0, ex = 0, ey = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                }
                if (grid[i][j] == 2) {
                    ex = i;
                    ey = j;
                }
                if (grid[i][j] != -1) {
                    todo++;
                }
            }
        }
        dfs(grid, sx, sy, ex, ey, todo);
        return ans;

    }

    private void dfs(int[][] grid, int x, int y, int endx, int endy, int todo) {
        todo--;
        if (todo < 0) {
            return;
        }
        if (x == endx && y == endy) {
            if (todo == 0) {
                ans++;
            }
            return;
        }
        for (int i = 0; i < 4; i++) {
            int tx = x + rows[i];
            int ty = y + cols[i];
            if (tx < 0 || ty < 0 || tx >= grid.length || ty >= grid[0].length || grid[tx][ty] % 2 != 0) {
                continue;
            }
            int origin = grid[tx][ty];
            grid[tx][ty] = -1;
            dfs(grid, tx, ty, endx, endy, todo);
            grid[tx][ty] = origin;
        }
    }

    //2. 记忆化搜索 TODO

    /*
     * #problem 32 最长有效括号
     * */
    // 1. 贪心算法
    public int longestValidParentheses(String s) {
        int left = 0, right = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (right == left) {
                max = Math.max(max, right);
            } else if (right > left) {
                left = 0;
                right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (right == left) {
                max = Math.max(max, right);
            } else if (left > right) {
                left = 0;
                right = 0;
            }
        }
        return max == Integer.MAX_VALUE ? 0 : max * 2;
    }

    // 2. 动态规划
    /*
     * dp[i] : 以s[i]结尾的最长有效括号长度
     * dp[i]的值来源有两种情况： 当 s[i] = ')' 且 s[i-1] = '(' ==> 那么 dp[i] = dp[i-2] + 2 [i和i-1]构成一个'()'是一个有效的括号，再加上以s[i-2]结尾的有效括号字符
     * 当s[i] = ')' 且 s[i-1] = ')'时，此时假设 s[i-1] = ')' 是包含在一个有效的括号字符串中（也就是dp[i-1]) ,那么 s[i]=')'一定有一个与之匹配的'('，这个括号应该在dp[i-1]的有效括号的前面
     * 也就是 s[i-dp[i-1]-1] 如果等于 '(' ==> 此时正好可以与 s[i]进行匹配。如果可以匹配的话，那么就只需要在加上 dp[i-dp[i-1]-2]的值即可
     * dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2  ==> +dp[i-dp[i-1]-2]的值是为了保证得到一个最长的子序列
     * */
    public int longestValidParentheses2(String s) {
        int[] dp = new int[s.length()];
        int max = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = 2 + (i >= 2 ? dp[i - 2] : 0);
                } else {
                    if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + 2 + (i - dp[i - 1] - 2 >= 0 ? dp[i - dp[i - 1] - 2] : 0);
                    }
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }

    /*
     * #problem 64 最小路径和
     * */
    // 1. 动态规划
    public int minPathSum(int[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        int[][] dp = new int[row][col];
        dp[row - 1][col - 1] = grid[row - 1][col - 1];
        for (int i = col - 2; i >= 0; i--) {
            dp[row - 1][i] = dp[row - 1][i + 1] + grid[row - 1][i];
        }
        for (int i = row - 2; i >= 0; i--) {
            dp[i][col - 1] = dp[i + 1][col - 1] + grid[i][col - 1];
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = col - 2; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i + 1][j], dp[i][j + 1]) + grid[i][j];
            }
        }
        return dp[0][0];
    }

    /*
     * #problem 91 解码方法
     * */
    // 1.DFS + 记忆化搜索
    public int numDecodings(String s) {
        int[] count = new int[s.length()];
        return numDecodingDfs(s, 0, count);
    }

    private int numDecodingDfs(String s, int pos, int[] count) {
        if (pos == s.length()) {
            return 1;
        }
        if (count[pos] != 0) {
            return count[pos];
        }
        int ans = 0;
        int t1 = Integer.valueOf(s.substring(pos, pos + 1));
        if (t1 != 0) {
            ans = numDecodingDfs(s, pos + 1, count);
            if (t1 <= 2 && pos + 2 <= s.length()) {
                int t2 = Integer.valueOf(s.substring(pos, pos + 2));
                if (t2 <= 26) {
                    ans += numDecodingDfs(s, pos + 2, count);
                }
            }
        }
        count[pos] = ans;
        return ans;
    }

    // 2. 动态规划
    public int numDecodings2(String s) {
        int[] dp = new int[s.length()];
        int t1 = Integer.valueOf(s.substring(0, 1));
        if (1 <= t1 && t1 <= 9) {
            dp[0] = 1;
        }
        for (int i = 1; i < s.length(); i++) {
            int temp = 0;
            int t = Integer.valueOf(s.substring(i, i + 1));
            if (t != 0) {
                temp = dp[i - 1];
            }
            t = Integer.valueOf(s.substring(i - 1, i + 1));
            if (t <= 26 && s.charAt(i - 1) != '0') {
                temp += (i - 2 >= 0 ? dp[i - 2] : 1);
            }
            dp[i] = temp;
        }

        return dp[s.length() - 1];
    }

    /*
     * #problem 221 最大正方形
     * */
    // 1. 动态规划
    /*
     * dp[i][j] : 以 [i,j]为右下角的最大正方形长度
     * dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
     * */
    public int maximalSquare(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        int[][] dp = new int[row][col];
        int max = 0;


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    }
                }
                max = Math.max(dp[i][j], max);
            }
        }
        return max * max;

    }

    /*
     * #problem 363 矩形区域不超过K的最大数值和
     * */
    // 1. 固定左右边界，利用前缀和
    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rows = matrix.length, cols = matrix[0].length, max = Integer.MIN_VALUE;
        // 固定左右边界
        for (int left = 0; left < cols; left++) {
            int[] rowSum = new int[rows];
            for (int right = left; right < cols; right++) {
                for (int i = 0; i < rows; i++) {
                    rowSum[i] += matrix[i][right];
                }
                // 求 最大数值和
                max = Math.max(max, dpMax(rowSum, k));
            }
        }
        return max;
    }

    // 求固定左右边界后的矩形最大值
    private int dpMax(int[] arr, int k) {
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < arr.length; begin++) {
            int sum = 0;
            for (int end = begin; end < arr.length; end++) {
                sum += arr[end];
                if (sum > max && sum <= k) {
                    max = sum;
                }
            }
        }
        return max;
    }

    // 2. 固定上下边界，算出每一列的和 （二维转一维） ==> 计算数组的最大区间和
    public int maxSumSubmatrix2(int[][] matrix, int k) {
        int ans = Integer.MIN_VALUE;
        int rows = matrix.length, cols = matrix[0].length;
        // 枚举上边界
        for (int begin = 0; begin < rows; begin++) {
            int[] sum = new int[cols];
            // 枚举下边界
            for (int end = begin; end < rows; end++) {
                // 计算每一列的和
                for (int i = 0; i < cols; i++) {
                    sum[i] += matrix[end][i];
                }
                // 获取到当前上下边界的 数组最大区间和
                TreeSet<Integer> sumSet = new TreeSet<>();
                sumSet.add(0);
                int s = 0;
                for (int v : sum) {
                    // s表示 sum[0] + sum[1] + ... + sum[r]
                    s += v;
                    // 需要根据 sum[r]找到其满足条件的 sum[l] ==> sum[r] - sum[l] <= k ==> sum[l] >= sum[r] - k
                    // ceiling(e) ==> 返回大于等于e的元素
                    Integer ceil = sumSet.ceiling(s - k);
                    if (ceil != null) {
                        // 可以找到对应的左边界
                        ans = Math.max(ans, s - ceil);
                    }
                    // 将当前前缀和加入到TreeSet ,方便后续的搜索
                    sumSet.add(s);
                }
            }

        }
        return ans;
    }

    /*
     * #problem 403 青蛙过河
     * */
    // 1. BFS 超时 ==> 因为到每块石头的k不同，所以不能用Set标记走过的石头，避免重复到达
    public boolean canCross(int[] stones) {
        if (stones.length == 2 && stones[1] == 1) {
            return true;
        }
        if (stones[1] != 1) {
            return false;
        }
        Deque<int[]> q = new LinkedList<>();

        Set<Integer> set = Arrays.stream(stones).boxed().collect(Collectors.toSet());
        q.add(new int[]{stones[1], 1});
        while (!q.isEmpty()) {
            int sz = q.size();
            while (sz-- > 0) {
                int[] qq = q.poll();
                int cur = qq[0];
                int k = qq[1];
                for (int i = k - 1; i <= k + 1; i++) {
                    if (i == 0) {
                        continue;
                    }
                    int next = cur + i;
                    if (next == stones[stones.length - 1]) {
                        return true;
                    }
                    if (set.contains(next)) {
                        q.offer(new int[]{next, i});
                    }
                }
            }
        }
        return false;

    }

    // 2. DFS + 记忆化搜索试试 ==> 为什么使用Map来进行记录结果会超时（奥因为int[]是不一样的)
    Map<Integer, Integer> stoneSet = new HashMap<>();
    Boolean[][] memo;

    public boolean canCross2(int[] stones) {
        if (stones.length == 2 && stones[1] == 1) {
            return true;
        }
        if (stones[1] != 1) {
            return false;
        }
        for (int i = 2; i < stones.length; i++) {
            stoneSet.put(stones[i], i);
        }
        memo = new Boolean[stones.length][stones.length];
        return dfsCross(stones, 1, 1);
    }

    /**
     * @param cur 当前走到哪块石头
     * @param k   使用的跳跃距离
     * @return 从该块石头出发是否可以到达最后一块石头
     */
    private boolean dfsCross(int[] stones, int cur, int k) {
        if (cur == stones.length - 1) {
            return true;
        }
        if (memo[cur][k] != null) {
            return memo[cur][k];
        }
        int curNum = stones[cur];
        boolean res = false;
        for (int len = k - 1; len <= k + 1 && !res; len++) {
            if (len <= 0) {
                continue;
            }
            int nextNum = curNum + len;
            if (stoneSet.containsKey(nextNum)) {
                res = res || dfsCross(stones, stoneSet.get(nextNum), len);
            }
        }
        memo[cur][k] = res;
        return res;
    }

    // 3. 动态规划
    // dp[i][k] ==> 以k的距离是否可以跳过第i块石头
    public boolean canCross3(int[] stones) {
        // 判断当前数组是否可达
        for (int i = 1; i < stones.length; i++) {
            // 在第i块石头上，最多可以跳i+1步
            if (stones[i] - stones[i - 1] > i) {
                return false;
            }
        }
        boolean[][] dp = new boolean[stones.length][stones.length];
        dp[0][0] = true;
        for (int i = 1; i < stones.length; i++) {
            // 枚举所有可能的上一块石头
            for (int j = i - 1; j >= 0; j--) {
                // 计算i与j的跳跃距离
                int k = stones[i] - stones[j];
                // 前面的石头也跳不过来了，停止枚举
                if (k > j + 1) {
                    break;
                }
                dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
                // 最后一块石头可达
                if (i == stones.length - 1 && dp[i][k]) {
                    return true;
                }
            }
        }
        return false;
    }


    /*
     * #problem 410 分割数组的最大值
     * */
    // 1. 动态规划
    /*
     * dp[i][j] ==> 将前i个数分割为j端的最小值
     * dp[i][j] ==> dp[k][j-1] + sub(k+1,i) 的值 ==> 遍历所有k的值，取最小值情况
     * 边界条件 ： i>=j ==> 如果 i<j,是无法切割为j段
     * dp[0][0] : 0 ==> 当j==1 ==> 前i个数被切割为一段. ==> k=0 表示这种情况,k!=0==>情况不符合，所以需要dp[0][0]的值作为推导条件
     * */
    public int splitArray(int[] nums, int k) {
        int len = nums.length;
        int[][] dp = new int[len + 1][k + 1];
        for (int i = 0; i <= len; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = 0;
        // 使用前缀和，加速区间求和过程
        int[] subSum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            subSum[i + 1] = subSum[i] + nums[i];
        }
        for (int i = 1; i <= len; i++) {
            for (int j = 1; j <= Math.min(i, k); j++) {
                // 遍历所有k的可能性
                for (int x = 0; x < i; x++) {
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[x][j - 1], subSum[i] - subSum[x]));
                }
            }
        }
        return dp[len][k];
    }

    // 2. 二分查找
    /*
     *  找到一个数x，满足x>= 最大分割子数组的和 且 分割数量为k
     * （题目固定m的值，让我们确定一个最大子数组和 ==> 限制一个最大子数组和max,反推：当最大子数组和为max时，至少可以将nums分割成几个子数组）
     *  判断是否满足的过程可以用贪心算法来实现 ：
     * 1. sum 表示当前分割子数组的和 cnt表示分割出的子数组的数量
     * 2. sum + num[i] > x ==> num[i] 作为新的子数组的开头 cnt+1
     * 3. 遍历结束，判断cnt <= m ==> cnt <= m ==> 说明 x过大 ， cnt > m ==> 说明x过小 (cnt<=m ==> 可以分为2个数组，那么肯定也可以分为3个数组）
     *  最小max ==> 左侧搜索边界 ==> 满足条件时，收缩右边界
     * */
    public int splitArray2(int[] nums, int k) {
        int left = 0, right = 0;
        for (int t : nums) {
            right += t;
            if (t > left) {
                left = t;
            }
        }
        // 搜索区间一般左闭右开
        right++;
        // 二分查找定位 x
        while (left < right) {
            int mid = (right - left) / 2 + left;
            if (check(nums, k, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean check(int[] nums, int k, int x) {
        int cnt = 1, sum = 0;
        for (int t : nums) {
            if (sum + t > x) {
                cnt++;
                sum = t;
            } else {
                sum += t;
            }
        }
        return cnt <= k;
    }

    /*
     * #problem 552 学生出勤记录II
     * */
    // 1.DFS --> 超时
    public int checkRecord(int n) {
        return checkRecordDFS(n, 0, 0, 0);
    }

    /**
     * @param n    需要的天数
     * @param cur  当天
     * @param aNum 缺勤次数
     * @param lNum 连续迟到次数
     * @return 出勤奖励
     */
    private int checkRecordDFS(int n, int cur, int aNum, int lNum) {
        if (cur == n) {
            return 1;
        }
        int res = 0;
        // 三种搜索情况
        // 1. 到场P
        res = checkRecordDFS(n, cur + 1, aNum, 0);
        // 2. 迟到
        if (lNum < 2) {
            res += checkRecordDFS(n, cur + 1, aNum, lNum + 1);
        }
        // 3. 缺勤
        if (aNum < 1) {
            res += checkRecordDFS(n, cur + 1, aNum + 1, lNum);
        }
        return res;
    }

    // 2. 动态规划
    /*
     * dp[i][j][k] : i:第i天
     * j: 0,1:缺勤次数
     * k:0,1,2 :连续迟到记录
     * dp[i][j][0] : ==> 连续迟到0天 --> 今天可以是缺勤，也可以是出勤（连续迟到天数中断）
     *  ==> dp[i-1][j][0] + dp[i-1][j][1] + dp[i-1][j][2] + dp[i-1][j-1][0] + dp[i-1][j-1][1]+dp[i-1][j-1][2]
     * dp[i][j][1~2] : ==> 连续迟到1~2 ==> 连续迟到天数不能断掉 ==> 只能是迟到
     * */
    public int checkRecord2(int n) {
        int[][][] dp = new int[n + 1][2][3];
        int mod = 1000000007;
        dp[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            // 当天为p ： 到场 ==> 连续迟到数清空为0 , 缺勤次数不变
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % mod;
                }
            }
            // 当天为A ： 缺勤 ==> 连续迟到数清空为0，缺勤次数 +1
            for (int k = 0; k < 3; k++) {
                dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % mod;
            }
            // 当天为L ： 迟到 ==> 连续迟到数+1，缺勤次数不变
            for (int j = 0; j < 2; j++) {
                for (int k = 1; k < 3; k++) {
                    dp[i][j][k] = dp[i - 1][j][k - 1] % mod;
                }
            }
        }
        int sum = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                sum = (sum + dp[n][j][k]) % mod;
            }
        }
        return sum;
    }

    /*
     * #problem 621 任务调度器
     * */
    // 1. 模拟
    public int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> freq = new HashMap<>();
        // key :任务类型 value:任务数量
        for (char c : tasks) {
            freq.put(c, freq.getOrDefault(c, 0) + 1);
        }
        // 不同类型的任务数
        int m = freq.size();
        // 两个数组，res 记录任务剩余执行次数  nextValid记录该任务下一次可执行的时间
        List<Integer> nextValid = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            int val = entry.getValue();
            nextValid.add(1);
            res.add(val);
        }
        // 模拟时间
        int time = 0;
        for (int i = 0; i < tasks.length; i++) {
            ++time;
            // 记录数组中的下一次可执行时间的最小值
            int minNextValid = Integer.MAX_VALUE;
            for (int j = 0; j < m; ++j) {
                if (res.get(j) != 0) {
                    minNextValid = Math.min(minNextValid, nextValid.get(j));
                }
            }
            // 只有当 当前时间小于 下一次可执行时间的最小值时 ==> 说明接下来都是处于待定状态 ==> 可以直接跳过
            time = Math.max(time, minNextValid);
            int best = -1;
            // 在数组中找到 <time 的可执行时间 && 剩余数量最多的任务
            for (int j = 0; j < m; j++) {
                if (res.get(j) != 0 && nextValid.get(j) <= time) {
                    if (best == -1 || res.get(j) > res.get(best)) {
                        best = j;
                    }
                }
            }
            nextValid.set(best, time + n + 1);
            res.set(best, res.get(best) - 1);
        }
        return time;

    }


    /*
     * #problem 647 回文子串
     * */
    // 1. 动态规划 dp[i][j]: i...j 是否为回文串
    public int countSubstrings(String s) {
        int len = s.length();
        int res = 0;
        boolean[][] dp = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                if (i == j) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]);
                }
                res += dp[i][j] ? 1 : 0;
            }
        }
        return res;
    }


    /*
     * #problem 76 最小覆盖子串
     * */
    // 1. 滑动窗口
    public String minWindow(String s, String t) {
        int min = Integer.MAX_VALUE;
        int start = 0, end = 0;
        if (s.length() < t.length()) {
            return "";
        }
        int len = t.length();
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        Map<Character, Integer> count = new HashMap<>();
        int left = 0, right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            // right 入队
            count.put(c, count.getOrDefault(c, 0) + 1);
            while (right - left + 1 >= len) {
                // 判断当前子串是否覆盖t
                if (judge(need, count)) {
                    if (min > right - left + 1) {
                        min = right - left + 1;
                        start = left;
                        end = right;
                    }
                    // 移动left ==> 出队
                    char r = s.charAt(left++);
                    count.put(r, count.get(r) - 1);
                } else {
                    break;
                }
            }
            right++;
        }

        return min != Integer.MAX_VALUE ? s.substring(start, end + 1) : "";
    }

    private boolean judge(Map<Character, Integer> need, Map<Character, Integer> cur) {
        for (Character c : need.keySet()) {
            if (!cur.containsKey(c)) {
                return false;
            }
            if (cur.get(c) < need.get(c)) {
                return false;
            }
        }
        return true;
    }

    // 2. 滑动窗口第二种写法
    public String minWindow2(String s, String t) {
        if (s.length() < t.length()) {
            return "";
        }
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> win = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0, start = 0, end = Integer.MAX_VALUE;
        int validate = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            int num = win.getOrDefault(c, 0) + 1;
            win.put(c, num);
            if (need.containsKey(c)) {
                if (need.get(c) == num) {
                    validate++;
                }
            }
            // 出队列
            while (need.size() == validate) {
                if (right - left < end - start) {
                    start = left;
                    end = right;
                }
                char r = s.charAt(left);
                num = win.get(r);
                if (need.containsKey(r) && need.get(r) == num) {
                    validate--;
                }
                win.put(r, num - 1);
                left++;
            }
            right++;
        }
        return end == Integer.MAX_VALUE ? "" : s.substring(start, end + 1);
    }

    /*
     * #problem 312 戳气球
     * */
    // 1. DFS + 记忆化搜索
    /*
     * 将戳气球转换为在一个 [left,right) 区间中 添加气球
     * */
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            temp[i] = nums[i - 1];
        }
        temp[0] = temp[n + 1] = 1;
        int[][] memo = new int[n + 2][n + 2];
        for (int i = 0; i < memo.length; i++) {
            Arrays.fill(memo[i], -1);
        }
        return solve(temp, 0, n + 1, memo);
    }

    // (left,right)区间中全部填满气球可以获得的最大硬币数
    //  left + 1 < right ==> 这样(left,right)区间中才有位置可以填气球
    private int solve(int[] nums, int left, int right, int[][] memo) {
        if (left >= right - 1) {
            return 0;
        }
        if (memo[left][right] != -1) {
            return memo[left][right];
        }
        // 枚举要添加的气球(第一个添加的气球）
        for (int mid = left + 1; mid < right; mid++) {
            int sum = nums[left] * nums[mid] * nums[right];
            sum += solve(nums, left, mid, memo) + solve(nums, mid, right, memo);
            memo[left][right] = Math.max(memo[left][right], sum);
        }
        return memo[left][right];
    }

    // 2. 动态规划
    /*
     * dp[i][j] ==> 戳破 (i,j)区间的所有气球可以获得的最大硬币数
     * 当 i >= right+1 时，dp[i][j] = 0 ==> 边界条件
     * */
    public int maxCoins2(int[] nums) {
        int n = nums.length;
        int[] temp = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            temp[i] = nums[i - 1];
        }
        temp[0] = temp[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        // 控制区间长度
        for (int i = 3; i <= n + 2; i++) {
            // 控制区间起始位置
            for (int j = 0; j < (n + 2 - i); j++) {
                // 遍历最后一步戳气球的点
                for (int k = j + 1; k < j + i - 1; j++) {
                    int val = temp[j] * temp[k] * temp[j + i - 1];
                    val += dp[j][k] + dp[k][j + i - 1];
                    dp[j][j + i - 1] = Math.max(dp[i][j], val);
                }
            }
        }
        return dp[0][n + 1];
    }


    /*
     * #problem 300 最长递增子序列
     * */
    // 1. DFS 每个位置选择或者不选择 ==> 超时
    private int max = Integer.MIN_VALUE;

    public int lengthOfLIS(int[] nums) {
        dfs(nums,0,new ArrayList<>());
        return max;
    }

    private void dfs(int[] nums, int cur, List<Integer> temp) {
        if (cur == nums.length) {
            max = Math.max(max,temp.size());
            return ;
        }
        if(temp.isEmpty() || nums[cur] > temp.get(temp.size()-1)) {
            temp.add(nums[cur]);
            dfs(nums,cur+1,temp);
            temp.remove(temp.size()-1);
        }
        dfs(nums,cur+1,temp);
    }

    // 2. 动态规划
    public int lengthOfLIS2(int[] nums) {
        int len = nums.length;
        int[] dp = new int[len];
        dp[0] = 1;
        int res = 1;
        for(int i =1;i<len;i++) {
            int max = 0;
            for(int j =0;j<i;j++) {
                if(nums[i] > nums[j]) {
                    max = Math.max(max,dp[j]);
                }
            }
            dp[i] = max +1;
            res = Math.max(res,dp[i]);
        }
        return res;
    }

    // 3. 贪心+二分查找
    /*
    * 让序列上升的坡度尽可能平缓
    * */
    public int lengthOfLIS3(int[] nums) {
        int len = 1,n = nums.length;
        if(n==0 || n == 1){
            return n;
        }
        // d[i] : 递增序列长度为i时，序列的最后一个元素的值
        int[] d = new int[n+1];
        d[len] = nums[0];
        for(int i =1;i<n;i++) {
            if(nums[i]  > d[len]) {
                d[++len] = nums[i];
            } else {
                // 找到子序列中第一个小于 nums[i]的元素 (此时将nums[i]插入到子序列中，len不需要更改）
                int l =1, r = len,pos = 0;
                while(l <= r) {
                    int mid = (r-l)/2 + l;
                    if(d[mid] <= nums[i]) {
                        pos = mid;
                        l = mid+1;
                    } else {
                        r = mid-1;
                    }
                }
                nums[pos+1] = nums[i];
            }
        }
        return len;
    }


    /*
    * #problem 85 最大矩形
    * */
    // 1. 暴力解法
    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length,m = matrix[0].length;
        int[][] left = new int[n][m];
        for(int j =0;j<m;j++) {
            for(int i =0;i<n;i++) {
                if(matrix[i][j] == '1') {
                    left[i][j] = (j==0) ? 1 : left[i][j-1] + 1;
                }
            }
        }
        int ans = 0;
        // 以(i,j)作为矩形的右下角，可以得到的最大值
        for(int i =0;i<n;i++) {
            for(int j =0;j<m;j++) {
                int width = left[i][j];
                int area = width;
                for(int k =i-1;k>=0;k--) {
                    width = Math.min(left[k][j],width);
                    area = Math.max(area,(i-k+1) * width);
                }
                ans = Math.max(ans,area);
            }
        }
        return ans;
    }

    // 2. 单调栈
    public int maximalRectangle2(char[][] matrix) {
        int n = matrix.length,m = matrix[0].length;
        int[][] left = new int[n][m];
        // 记录矩形宽度
        for(int j =0;j<m;j++) {
            for(int i =0;i<n;i++) {
                if(matrix[i][j] == '1') {
                    left[i][j] = (j==0) ? 1 : left[i][j-1] +1;
                }
            }
        }
        int res = 0;
        // 针对每一列，求最大值
        for(int j =0;j<m;j++) {
            // 针对当前行，求其上下边界（最近小于当前行的宽度）
            int[] up = new int[n];
            int[] down = new int[n];
            Arrays.fill(down,n);
            Deque<Integer> stack = new LinkedList<>();
            for(int i =0;i<n;i++) {
                int curWidth = left[i][j];
                while(!stack.isEmpty() && curWidth <= left[stack.peek()][j] ) {
                    int upIndex = stack.pop();
                    down[upIndex] = i;
                }
                up[i] = stack.isEmpty()?-1 : stack.peek();
                stack.push(i);
            }
            // 计算面积
            int area = 0;
            for(int i =0;i<n;i++) {
                int width = left[i][j];
                int height = down[i] - up[i] -1;
                area = Math.max(area,width*height);
            }
            res = Math.max(res,area);
        }

        return res;
    }

    /*
    * #problem 818 赛车
    * */
    /*
    *  position : 0 --> 1 --> 3 --> 5 --> 7  (2^n-1)
    *  speed : 1 --> 2 --> 4 --> 8 --> 16 (2^n)
    * dp[i] ==> 达到i位置的最短指令序列长度
    * 假设连续走了n步 ==> 会走到 2^n-1的位置，这样子到达i就会有多种情况：
    * 1. 2^n-1 == i ==> 直接到达i位置 ==> dp[i] = n
    * 2. 连续加速k次，越过了i的位置 ==> 2^k-1 > i ==> 此时需要回头
    * 回头需要一个R +1,从2^k-1 的位置要达到i，就要回头走 2^k-1 -i 步 ==> dp[2^k-1 -i] ==> dp[i] = k + 1 + dp[2^k-1-i]
    * 3. 还未达到i的位置，就回头，然后再达到i的位置,假设走了x次， (2^k-1 - [2^x-1])此时的位置 ,从该位置到达i==> dp[i - (2^k-1) + (2^x-1)]
    * dp[i] = k + 1 + x +1 + dp[i-(2^k-1)+(2^x-1)]
    * */
    public int racecar(int target) {
        if(target <= 0) {
            return 0;
        }

        int[] dp = new int[target+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        for(int i =1;i<=target;i++) {
            // 先向前走forward步
            for(int forward = 1;(1 << forward) -1 < 2*i;forward ++) {
                // 向前走了几步
                int forwardDistance = (1<<forward) -1;
                if(forwardDistance == i) {
                    dp[i] = forward;
                } else if(forwardDistance > i) {
                    // 走过头，往回走  +1是因为需要一个R指令
                    dp[i] = Math.min(dp[i],forward+1+dp[forwardDistance-i]);
                } else {
                    // 还没到i就往回走
                    for(int backward=0;backward<forward;backward++) {
                        int backwardDistance = (1<<backward)-1;
                        // 第一个+1是还没到达i，回头 使用R
                        // 第二个+1是回头走后，还要回头走到i
                        dp[i] = Math.min(dp[i],forward+1+backward+1+dp[i-forwardDistance+backwardDistance]);
                    }
                }
            }
        }
        return dp[target];
    }



}
